class Solution
{
public:
    int countPrimes(int n)
    {
        bool *isPrime = new bool[n];
        for (int i = 2; i < n; ++i)
        {
            isPrime[i] = true;
        }
        for (int i = 2; i < n; ++i)
        {
            if (isPrime[i])
            {
                for (int j = i; j * static_cast<long long>(i) < n; ++j)
                {
                    isPrime[j * i] = false;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; ++i)
        {
            count += static_cast<int>(isPrime[i]);
        }
        delete[] isPrime;
        return count;
    }
};